%# -*- coding: utf-8-unix -*-
%%==================================================
%% chapter01.tex for BJTU Master Thesis
%%==================================================

%\bibliographystyle{bjtu}%[此处用于每章都生产参考文献]
\chapter{基于网络模型的铁路动态价格模型与算法}
\label{chap:Chapter5}

本章从网络模型的角度，研究制定铁路动态价格的方法。采用网络模型的关键问题在于如何构建状态网络表达旅客行为和产品价格变化，以及如何在数学模型中关联这两类网络。

\section{状态网络构建}

这一节介绍引入动态价格控制和旅客行为的状态网络表达。状态网络表达的基本思想是枚举动态价格控制系统和旅客出行的所有可能的状态。通过引入高维网络，状态之间的转移可以通过连接两个节点的弧段表达。对于动态价格控制系统来说，一个动态价格策略可以通过价格-时间网络中的路径表示；对于一个旅客来说，其出行的路径可以通过价格-时空网络中的路径来表示。通过对动态价格控制系统和每个旅客分别建立一个状态网络，动态价格问题就转变为网络路径问题。本节首先介绍如何分别为动态价格控制系统和旅客构建状态网络。本章采用的符号如表\ref{tab:5-1}所示。

\begin{table}[htbp]
\centering
\bicaption[tab:5-1]{符号列表}{符号列表}{Table}{Symbol list}
\begin{tabular}{ll}
	\hline
	符号                            & 描述                                            \\ \hline
	$a$                           & 旅客                                            \\
	$M$                           & 列车的集合，通过 $m \in M$ 索引                         \\
	$I$                           & 车站的集合，通过 $i,i',j$ 索引                          \\
	$o(a)$                        & 旅客 $a$ 的出发车站                                  \\
	$d(a)$                        & 旅客 $a$ 的目的车站                                  \\
	$T$                           & 离散的时间段，通过 $t,t',\tau,\tau'$ 索引                \\
	$K$                           & 离散的价格档位集合， 通过 $k,k',h,h'$ 索引                  \\
	$k_0$                         & 表示预订状态的虚拟价格档位                                 \\ \hline
	\textbf{价格-时空网络}              &                                               \\ \hline
	$(V,E)$                       & 价格-时空网络，其中 $V$ 表示节点集合， $E$ 表示弧段集合             \\
	$(i,t,k)$                     & 价格-时空网络中的节点，通过 $(i,t,k) \in V$ 索引             \\
	$(i,i',t,t',k,k')$            & 价格-时空网络中的弧段，通过 $(i,i',t,t',k,k') \in E$ 索引    \\
	$c_{i,i',t,t',k,k'}$          & 弧段 $(i,i',t,t',k,k')$ 的费用                     \\
	$\bar E_{train}$              & 列车服务区段的集合，通过 $(i,i',t,t')$ 索引                 \\
	$Cap_{i,i',t,t'}$             & 列车服务区段 $(i,i',t,t')$ 的席位数量                    \\
	$l$                           & 价格-时空网络中的路径                                   \\
	${\Omega \left( a \right)}$   & 旅客 $a$ 的所有可行路径的集合                             \\
	${\Phi \left( {a,l} \right)}$ & 旅客 $a$ 的第 $l$ 条可行路径中的弧段集合                     \\
	$\varepsilon (a) $            & 旅客 $a$ 所能接受的偏离最小花费路径的值                        \\
	$\delta_{i,i',t,t',k,k'}^m$   & 0-1变量，取值为1表示弧段 ${i,i',t,t',k,k'}$ 是预约列车 $m$   \\
	                              & 的预订弧段                                         \\
	$E_{res}$                     & 预订弧的集合                                        \\
	$z_{i,i',t,t',k,k'}^a$        & 旅客选择 $(i,i',t,t',k,k')$ 弧的收益                  \\
	$M,M'$                        & 很大的正整数                                        \\ \hline
	\textbf{价格-时间网络}              &                                               \\ \hline
	$(V',E')$                     & 价格-时间网络                                       \\
	$(\tau,k)$                    & 价格-时间网络中的节点                                   \\
	$(\tau,\tau',k,k')$           & 价格-时间网络中的弧段                                   \\ \hline
	\textbf{决策变量}                 &                                               \\ \hline
	$x_{i,i',t,t',k,k'}^a$        & 0-1变量，取值为1表示旅客 $a$ 选择弧段 $(i,i',t,t',k,k')$ 出行 \\
	$y_{i,i',t,t',k,k'}^a$        & 0-1变量，取值为1表示弧段 $(i,i',t,t',k,k')$ 开放          \\
	$w_{\tau,\tau',h,h'}^{i,m}$   & 0-1变量，取值为1表示价格列车$m$在车站$i$的价格-时间网络             \\
	                              & 弧段$\tau,\tau',h,h'$被选择                        \\ \hline
\end{tabular}
\end{table}

\subsection{价格-时间网络}

在构建价格-时间网络之前，先要考虑铁路车票的价格结构。在第三章介绍我国铁路采用基于里程的定价方式，即每一个列车服务区段有一个成本价格，一张车票的价格等于它经过的列车服务区段的成本价格之和（暂时忽略“递远递减”）。目前车票价格调整手段主要是通过在基础的车票价格上按照一定的百分比增减，即列车服务区段的成本价格会存在多个价格等级。在预售期的每个时间段，铁路企业都要决定每列车不同OD的车票价格等级。

动态价格控制可以认为是决定每个时间段每个产品的价格等级。本章假设所有可能的价格等级是预设的，且价格等级的调整是根据产品的始发站统一进行调整。图\ref{fig:5-2}(a)展示了5个价格等级( -20\%, -10\%, 基础价格, +10\%, +20\%)之间的转化关系，这里为了使得价格能够平稳变化，限制了每次价格的调整幅度。如果当前价格等级为基础价格，那么下一次调整中它可以从 \{ -10\%, 基础价格, +10\% \} 中选择。

通过建立价格-时间网络，价格调整问题可以转化为网络设计问题\cite{LiMirchandani-929,LiuZhou-931}。假设一个铁路路网由车站和区间构成。令 $I$ 表示铁路车站的集合，通过 $i \in I$ 索引。价格等级通过 $k \in K = \{ {k_1,k_2,...}\}$ 表示。车票价格等级随时间的变化可以通过价格-时间网络表达。对于列车$m$始发站为$i$的产品价格变化，可以通过价格-时间网络 $\left( {V',E'} \right)$ 表示。其中节点记为 $(\tau,k) \in V'$，表示在 $\tau$ 时刻价格等级为 $k$；网络中弧段记为 $(\tau ,\tau ',k,k')$，表示在 $\tau$ 至 $\tau'$ 时间段内价格等级为 $k$，然后价格等级在 $\tau'$ 时刻变为 $k'$。通过网络表达，价格等级的变化可以通过价格-时间网络中的一条路径来表示。为了保证所有的价格-时间路径都从同一个起点出发并回到终点。这里增加一个虚拟起点 $(-1,k_0)$ 和 一个虚拟的终点 $(T_R+1,k_0)$。

图\ref{fig:5-2}(a) 展示了5个价格等级的可行调整范围。例如处于价格等级 $k_1$ 时，下一阶段价格只能调整到价格等级 $k_2$ 或者继续保持 $k_1$。图\ref{fig:5-2}(b)展示了对应图\ref{fig:5-2}(a)的价格-时间网络，其中价格调整的频率为10个单位时间。

\begin{figure}[H]
\centering
\includegraphics[width=\textwidth]{Fig_5-2.png}
\bicaption[fig:5-2]{价格-时间网络}{价格-时间网络}{Fig}{Price-time network}
\end{figure}

\subsection{旅客行为的路径表示}

预售期开始时，列车的时刻表和车底运用计划固定，不同OD旅客进入订票系统进行购票。对于一个旅客来说，他进入购票系统的时间（“到达时间”）、出发地和目的地都是已知的。这位旅客在购票的过程中可以做两类选择，第一，决定何时购票；第二，决定购买何种车票。

根据第二章提出的建模框架，预售期被当作是一个离散时间的过程。离散的时间通过$t$索引。这里考虑的时间除了预售期外，还增加了列车运行的时间。此模型考虑的时间包含两部分：预售期（从 $t=0$ 到 $t=T_R$ ）和列车运行时期（从 $t=T_R+1$ 至 $t=T$）。这两部分的时间可以有不同的尺度（一个时间段与真实时间的比例）。对于预售期，这取决于需求预测能够到达的精度。对于列车运行时期，时间的尺度通常按分钟计。作为问题的输入，每个旅客的到达时间都被归于一个离散时间。假设旅客的到达时间为$T^a$。

旅客的订票和出行可以用一系列连续的状态变化来表达。通过构建状态网络可以将旅客的选择表达为交通分配问题。文献\parencite{LiuZhou-931}建立了一个离散时间的时空网络模型来表达交通网络设计的问题。本章将这个模型拓展为价格-时空网络来表达旅客预定和出行行为。一个价格-时空网络记为$(V,E)$，其中 $V$ 是节点集合，$E$是弧段集合。其中一个节点表示为 $(i,t,k)$，一个弧段记为 $(i,i',t,t',k,k')$。为了考虑预定时的等待成本，这里引入一个虚拟的价格等级 $k_0$。拓展后的价格等级的集合记为 $K' = K  \cup \{ {k_0} \}$。

旅客$a$的出发节点可以表示为 $(o(a),T^a,k_0)$，其中 $o(a)$ 是旅客的出发的车站，$T^a$ 是旅客开始购票的时间。旅客的订票和出行的行为可以通过以下6种弧段表示：

\begin{itemize}
\item \textbf{预定弧段} \ 预定弧段 $(i,i,t,t',k_0,k')$ 表示在时间段 $t$ 购票。注意不是所有的预定弧段在时间段$t$都是可行的———动态的价格对旅客的影响表现为可以开放或关闭预定弧段。
\item \textbf{乘车弧段} \ 乘车弧段 $(i,i',t,t',k,k)$ 表示旅客乘坐列车经过列车服务区段 $i$ - $i'$。
%\item \textbf{Transfer link.} A transfer link $(i,i,t,t',k,k)$ represents the transfer in station $i$.
\item \textbf{等待弧段} \ 等待弧段 $(i,i,t,t+1,k_0,k_0)$ 表示旅客从进入购票系统到购得车票的等待时间。
\item \textbf{到达弧段} \ 到达弧段 $(i,i,t,T,k,k_0)$ 是每个旅程的最后一段，它保证了具有相同目的地车站 $i$ 的旅客路径会到达最终节点 $(i,T,k_0)$。
%\item \textbf{Dummy link.} A dummy link $(i,i',t,T,k_0,k_0)$ represents giving up the travel plan.
\end{itemize}

对于给定的时刻表，如图\ref{fig:5-1}(a)所示，假设一共有三个价格等级$\{ k_1, k_2, k_3 \}$。都可以构建一个价格-时空网络来表达旅客的行为，如图\ref{fig:5-1}(b)所示。

\begin{figure}[htbp]
\centering
\includegraphics[width=\textwidth]{Fig_5-1.png}
\bicaption[fig:5-1]{时刻表与价格-时空网络示意}{时刻表与价格-时空网络示意}{Fig}{An example of timetable and price-space-time network}
\end{figure}

对于每条弧段，都要考虑其出行成本 $c_{i,i',t,t',k,k'}$，它表示旅客预定、乘车的行为的开销。在本章中，出行成本主要包括时间和车票的价格。通过时间价值(value-of-time, VOT)可以把成本统一按照价格计算。

\section{模型构建}

通过引入采用状态网络，动态价格问题可以表达为网络构建问题形式。问题的决策变量可以分为两类：第一，旅客的路径 $X = \left\{ {x_{i,i',t,t',k,k'}^a} \right\}, \forall a$；第二，价格等级变化路径 $W = \left\{ {w_{\tau,\tau',k,k'}^{i,m}} \right\}$。其中 $x_{i,i',t,t',k,k'}^a$ 为0-1变量，如果旅客 $a$ 选择了弧段 $(i,i',t,t',k,k')$ 其值为1，反之为0。$w_{\tau,\tau',k,k'}^{i,m}$ 也是0-1变量，如果列车 $m$ 的从车站 $i$ 出发的产品在时间段 $(\tau,\tau')$的价格等级为 $k$且之后调整为 $k'$，其取值为1，反之为0。为了便于表达，这里引入一个0-1辅助变量 $y_{(i,i,t,t',k_0,k')}$，如果预定弧段 $(i,i,t,t',k_0,k')$ 开放其值取1，反之取0。显然，$y_{(i,i,t,t',k_0,k')}$ 的值取决于 $w_{\tau,\tau',k,k'}^{i,m}$。

\textbf{(1)目标函数}

本章的目标函数是使得售票收入最大化，它等于所有旅客选择的乘车弧段的价格的总和。令 ${z'}_{i,i',t,t',k,k'}^a$ 表示旅客 $a$ 通过弧段 $(i,i',t,t',k,k')$ 的花费。目标函数可以通过式(\ref{obj-fun})表示。
\begin{equation}
\max_{\boldsymbol{x}} z\left( \boldsymbol{x} \right) = \sum\limits_a {\sum\limits_{(i,i',t,t',k,k') \in E} {{z'}_{i,i',t,t',k,k'}^ax_{i,i',t,t',k,k'}^a} } 
\label{obj-fun}
\end{equation}
出于表达习惯考虑，在下文中把目标从"Max" 改为 "Min"，并且取$z_{i,i',t,t',k,k'}^a = -{z'}_{i,i',t,t',k,k'}^a$。目标函数改为了最小化的形式。

\textbf{(2)流平衡约束}

价格-时空网络节点 $(i,t,k)$ 的流平衡可写为式(\ref{passenger-conservation})。它表示旅客 $a$ 除了出发节点和终到节点外，每次进入一个中途节点都必然要退出。
\begin{equation}
\begin{split}
& \sum\limits_{i',t',k':\left( {i,i',t,t',k,k'} \right) \in E} {x_{i,i',t,t',k,k'}^a}  - \sum\limits_{i',t',k':\left( {i',i,t',t,k',k} \right) \in E} {x_{i',i,t',t,k',k}^a}  \\
& = \begin{cases}
  1   & {i = o\left( a \right),t = {T^a},k = {k_0}} \\
  -1 & {i = d\left( a \right),t = T,k = {k_0}} \\ 
  0 & \text{其它} 
\end{cases}
,\;\;\;\forall a,i,t,k
\end{split}
\label{passenger-conservation}
\end{equation}

\textbf{(3)列车能力约束}

令 $({i,i',t,t'})$ 表示一个列车服务区段。所有使用这条列车服务区段的旅客人数应该小于它的席位数上限 $Cap_{{i,i',t,t'}}$。列车能力约束如式(\ref{capacity})所示。
\begin{equation}
\sum\limits_a {\sum\limits_{k,k'} {x_{i,i',t,t',k,k'}^a \le Ca{p_{i,i',t,t'}}} } ,\;\;\;\forall (i,i',t,t') \in {{\bar E_{train}}}
\label{capacity}
\end{equation}

\textbf{(4)旅客的有限理性约束}

通过价格-时空网络的表达，旅客可以选择任意一条路径出行。然而在给定了动态价格策略之后，有些出行路径成本明显比其它的路径高很多。作为理性选择的旅客会尽可能的不选择高成本的路径出行。文献\parencite{LiuZhou-931}采用有限理性(boundedly rational)约束来表达旅客的这种选择行为。本章沿用这一思路，对于旅客 $a$, 如果路径 $l$ 的成本在能够容忍程度内，他/她才会选择这条路径出行。有限理性约束通过式(\ref{indifferenceband})表达。
\begin{align}
& {c_a} \le \mathop {min}\limits_{l \in \Omega \left( {a} \right)} \left\{ {{c_{a,l}}} \right\} + \varepsilon \left( a \right),\;\;\;\forall a
\label{indifferenceband} \\
& {c_a} = \sum\limits_{\left( {i,i',t,t',k,k'} \right) \in E} {{c_{i,i',t,t',k,k'}}} x_{i,i',t,t',k,k'}^a
\label{passengercost}\\
& {c_{a,l}} = \sum\limits_{\left( {i,i',t,t',k,k'} \right) \in \Phi \left( {a,l} \right)} {\left[ {{c_{i,i',t,t',k,k'}} + \left( {1 - {y_{i,i',t,t',k,k'}}} \right)M} \right]} ,\;\;\;\forall l \in \Omega \left( a \right)
\label{passengerroutecost}
\end{align}
\begin{itemize}
\item 令 ${c_a}$ 表示旅客 $a$ 的总花费，可以通过 (\ref{passengercost})计算。
\item 令 ${c_{a,l}}$ 表示旅客 $a$ 选择路径 $l$ 的花费，它可由式(\ref{passengerroutecost})计算。如果路径中存在不开放的预定弧段，通过引入一个非常大的正数 $M$ 作为这个不可行的弧段花费。
\item $\varepsilon \left( a \right)$ 表示旅客 $a$ 对花费偏离最小费用路径的容忍程度。
\item $\Omega \left( {a} \right)$ 表示旅客 $a$ 所有可行路径。
\item $\Phi \left( {a,l} \right)$ 表示旅客 $a$ 的路径 $l$ 包含的所有价格-时空网络的弧段集合。
\end{itemize}

通过合并以上的三个式子，有限理性约束可以写为式(\ref{brue})。
\begin{equation}
\begin{split}
\sum\limits_{\left( {i,i',t,t',k,k'} \right) \in E} {{c_{i,i',t,t',k,k'}}} x_{i,i',t,t',k,k'}^a \le & \sum\limits_{\left( {i,i',t,t',k,k'} \right) \in \Phi \left( {a,l} \right)} {\left[ {{c_{i,i',t,t',k,k'}} + \left( {1 - {y_{i,i',t,t',k,k'}}} \right)M} \right]} \\
& + \varepsilon \left( a \right),\;\;\;\forall a,l \in \Omega \left( a \right)
\end{split}
\label{brue}
\end{equation}

\textbf{(5)动态价格逻辑约束}

在售票过程中，假设每次一张车票只有一个价格。通过构造价格-时空网络，对于时间段 $t$ 的车站 $i$，在一簇预定弧段 $E_{res}  = \left\{(i,i,t,t',k_0,k'),\forall k' \in K \right\}$ 中只有一条是开放的。预定弧段的开放情况 $y_{i,i,t,t',{k_0},k}$ 与动态价格系统中的控制策略 $w_{\tau ,\tau ',k,k'}^i$ 的关系可以表示为式(\ref{price-control})。

\begin{equation}
{y_{i,i',t,t',k,k'}} = 
\begin{cases}
\sum\limits_{h \in K} {\sum\limits_{\tau  \leqslant t} {\sum\limits_{\tau ' > t} {\sum\limits_m {\delta _{i,i',t,t',k,k'}^mw_{\tau ,\tau ',k',h}^{i,m}} } } } & \forall \left( {i,i',t,t',k,k'} \right) \in {E_{res}}\\
1 & \text{其他}
\end{cases}
\label{price-control}
\end{equation}
\begin{itemize}
\item ${\delta _{i,i',t,t',k,k'}^m} =1$ 表示 $(i,i',t,t',k,k')$ 是列车 $m$ 的一个预定弧段。
\end{itemize}
\begin{equation}
\begin{split}
& \sum\limits_a {x_{i,i',t,t',k,k'}^a}  \le {y_{i,i',t,t',k,k'}}M', \\
& \forall (i,i',t,t',k,k') \in {E_{res}}
\end{split}
\label{reservation-constraint}
\end{equation}

除了以上的约束之外，还要引入式(\ref{price-path}) 表示价格-时间网络中的路径流量守恒约束。
\begin{equation}
\sum\limits_{\tau ',k':\left( {\tau ,\tau ',k,k'} \right) \in E'} {w_{\tau ,\tau ',k,k'}^{i,m}}  - \sum\limits_{\tau ',k':\left( {\tau ',\tau ,k',k} \right) \in E'} {w_{\tau ',\tau ,k',k}^{i,m}}  = \begin{cases}
1 & {\tau  = -1,k = {k_0}}\\
{ - 1} & {\tau  = {T_R+1},k = {k_0}}\\
0 & \text{其他}
\end{cases},\\
\;\;\;\forall i, \tau, k, m
\label{price-path}
\end{equation}

这里的决策变量都为0-1变量，可写为式(\ref{bin1})和(\ref{bin2})。
\begin{eqnarray}
 x_{i,i',t,t',k,k'}^a = \{0,1\},\;\;\; \forall a,i,i',t,t',k,k'
\label{bin1}\\
w_{t,t',k,k'}^{i,m} = \{0,1\},\;\;\; \forall i,t,t',k,k',m
\label{bin2}
\end{eqnarray}

综上所述，铁路车票动态价格问题可以写为目标为  (\ref{obj-fun}) 且约束为 (\ref{passenger-conservation}), (\ref{capacity}), (\ref{brue}), (\ref{price-control}), (\ref{price-path}), (\ref{bin1}) 和 (\ref{bin2}) 的0-1数学规划问题。

\section{求解方法}

对于以上的0-1规划问题，它可以通过精确算法，如分支定界算法求解。然而，随着问题规模的扩大，采取分支定界算法需要的求解时间也会急剧增长。本节运用拉格朗日启发式方法求解问题，它的基本思路是通过求解拉格朗日乘子问题并且通过解修复方法得在较短的时间内得到一个近似可行解。

采用拉格朗日启发式方法的第一步是对于约束(\ref{capacity}), (\ref{brue}) 和 (\ref{reservation-constraint})引入拉格朗日乘子 ${\rho_{i,i',t,t'}}$, ${\mu _{a,l}}$ 和 $\lambda _{i,i',t,t',k,k'}$。拉格朗日函数可以写为式(\ref{LagrangianFunction})。
\begin{equation}
\begin{split}
&L\left( {\boldsymbol{x},\boldsymbol{w},\boldsymbol{\mu},\boldsymbol{\rho},\boldsymbol{\lambda}} \right) = \sum\limits_a {\sum\limits_{(i,i',t,t',k,k') \in E} {{z_{i,i',t,t',k,k'}^a}x_{i,i',t,t',k,k'}^a} } \\
&\ \ \ \ + \sum\limits_a \sum\limits_{l \in \Omega \left( a \right)} \mu _{a,l} \left\{  \sum\limits_{\left( {i,i',t,t',k,k'} \right) \in E} c_{i,i',t,t',k,k'} x_{i,i',t,t',k,k'}^a - \right.\\
&\ \ \ \ \left. \sum\limits_{\left( {i,i',t,t',k,k'} \right) \in \Phi \left( {a,l} \right)} \left[ c_{i,i',t,t',k,k'} + \left( 1 - y_{i,i',t,t',k,k'} \right)M \right]  - \varepsilon \left( a \right) \right\} \\
& \ \ \ \ + \sum\limits_{(i,i',t,t') \in {\bar E_{train}}} {{\rho _{i,i',t,t'}}\left[ {\sum\limits_a {\sum\limits_{k,k'} {x_{i,i',t,t',k,k'}^a - {Cap}_{i,i',t,t'}} } } \right]} \\
& \ \ \ \ + \sum\limits_{(i,i',t,t',k,k') \in E_{res}} {{\lambda _{i,i',t,t',k,k'}}\left( {\sum\limits_a {x_{i,i',t,t',k,k'}^a}  - {y_{i,i',t,t',k,k'}}M'} \right)} 
\end{split}
\label{LagrangianFunction}
\end{equation}

对偶函数 $q(\boldsymbol{\mu},\boldsymbol{\rho},\boldsymbol{\lambda})$ 定义为拉格朗日松弛问题(Lagrangian relaxation problem, LR-RDP)的最优解，如式(\ref{dual-function})所示。
\begin{equation}
q({\bf{\mu }},{\boldsymbol{\rho }},{\boldsymbol{\lambda }}) = \mathop {\mathop {min}\limits_{({\boldsymbol{x}},{\boldsymbol{w}}) \in P} L\left( {{\boldsymbol{x}},{\boldsymbol{w}},{\boldsymbol{\mu }},{\boldsymbol{\rho }},{\boldsymbol{\lambda }}} \right)}\limits 
\label{dual-function}
\end{equation}
\begin{itemize}
\item $P$ 表示使得约束(\ref{passenger-conservation}), (\ref{price-control}), (\ref{price-path}), (\ref{bin1}) 和 (\ref{bin2}) 成立的路径 $({\boldsymbol{x}},{\boldsymbol{w}})$ 的集合。
\end{itemize}

第二步就是求解拉格朗日乘子问题(\ref{multiplier-problem})得到 $({\boldsymbol{x}}^*,{\boldsymbol{w}}^*)$ 的值。注意，由于松弛了部分约束，拉格朗日乘子问题的解 $({\boldsymbol{x}}^*,{\boldsymbol{w}}^*)$ 对于原问题来说可能是不可行的。但是它为原问题提供了一个下界。这个过程可以通过分解拉格朗日函数并行计算来加速(在\ref{decom-Lag}小节介绍)。通过解修复方法 (在 \ref{sol-fix}小节介绍) 可以得到问题的一个可行解。而且这个可行解的质量可以通过与下界比较而反映出来。

\begin{equation}
\begin{split}
& \mathop {\max }\limits_{{\boldsymbol{\mu}},{\boldsymbol{\rho}},{\boldsymbol{\lambda}} \geqslant 0} q \left( {{\boldsymbol{\mu}},{\boldsymbol{\rho}},{\boldsymbol{\lambda}}} \right)
\label{multiplier-problem}
\end{split}
\end{equation}

通常求解拉格朗日乘子问题可以采用两种方法，分别是次梯度法和割平面法。这两种方法的思想都是在迭代的过程中不断更新拉格朗日乘子。次梯度法的细节会在\ref{sub-gra}小节介绍。割平面法的细节会在\ref{cuttingplane}小节介绍。

\subsection{拉格朗日松弛问题的分解} \label{decom-Lag}

拉格朗日松弛问题可以分解为两个能够高效求解的问题。在拉格朗日函数 $L\left( {\boldsymbol{x},\boldsymbol{w},\boldsymbol{\mu},\boldsymbol{\rho},\boldsymbol{\lambda}} \right)$ 中有两项与 $y_{i,i',t,t',k,k'}$ 有关，它们是
$\sum\limits_a {\sum\limits_{l \in \Omega \left( a \right)} {\sum\limits_{\left( {i,i',t,t',k,k'} \right) \in \Phi \left( {a,l} \right)} {{\mu _{a,l}}{y_{i,i',t,t',k,k'}}M} } }  $ 和 $\sum\limits_{(i,i',t,t',k,k') \in E} {{\lambda _{i,i',t,t',k,k'}}{y_{i,i',t,t',k,k'}}M'} $。下面对这两项进行变换。
\begin{equation}
\begin{split}
 & \sum\limits_a {\sum\limits_{l \in \Omega \left( a \right)} {\sum\limits_{\left( {i,i',t,t',k,k'} \right) \in \Phi \left( {a,l} \right)} {{\mu _{a,l}}{y_{i,i',t,t',k,k'}}M} } }  - \sum\limits_{(i,i',t,t',k,k') \in E} {{\lambda _{i,i',t,t',k,k'}}{y_{i,i',t,t',k,k'}}M'}  
\\
& (\text{交换第二和第三项})\\
= & \sum\limits_a {\sum\limits_{\left( {i,i',t,t',k,k'} \right) \in E} {\sum\limits_{l \in \Omega \left( a \right)} {{1_{\left\{ {\left( {i,i',t,t',k,k'} \right) \in \Phi \left( {a,l} \right)} \right\}}}{\mu _{a,l}}{y_{i,i',t,t',k,k'}}M} } }  - \sum\limits_{(i,i',t,t',k,k') \in E} {{\lambda _{i,i',t,t',k,k'}}{y_{i,i',t,t',k,k'}}M'} \\
& (\text{交换第一和第二项})\\
= & \sum\limits_{\left( {i,i',t,t',k,k'} \right) \in E} {\sum\limits_a {\sum\limits_{l \in \Omega \left( a \right)} {{1_{\left\{ {\left( {i,i',t,t',k,k'} \right) \in \Phi \left( {a,l} \right)} \right\}}}{\mu _{a,l}}{y_{i,i',t,t',k,k'}}M} } }  - \sum\limits_{(i,i',t,t',k,k') \in E} {{\lambda _{i,i',t,t',k,k'}}{y_{i,i',t,t',k,k'}}M'} \\
= & \sum\limits_{(i,i',t,t',k,k') \in E} {\left( {\sum\limits_a {\sum\limits_{l \in \Omega \left( a \right)} {{1_{\left\{ {(i,i',t,t',k,k') \in \Phi \left( {a,l} \right)} \right\}}}{\mu _{a,l}}M}  - {\lambda _{i,i',t,t',k,k'}}M'} } \right)} {y_{i,i',t,t',k,k'}}
\end{split} \nonumber
\end{equation}

综上，通过整理朗格朗日函数 $L\left( {\boldsymbol{x},\boldsymbol{w},\boldsymbol{\mu},\boldsymbol{\rho},\boldsymbol{\lambda}} \right)$ 可得式 (\ref{LR-rearrangement})。
\begin{equation}
\begin{split}
& L\left( {\boldsymbol{x},\boldsymbol{w},\boldsymbol{\mu},\boldsymbol{\rho},\boldsymbol{\lambda}} \right) \\
& = \sum\limits_a {\sum\limits_{(i,i',t,t',k,k') \in E} { \Bigg [{z_{i,i',t,t',k,k'}^a} + \sum\limits_{l \in \Omega \left( a \right)} {{\mu _{a,l}}} {c_{i,i',t,t',k,k'}} + {\rho _{i,i',t,t'}} \cdot {1_{\left\{ {(i,i',t,t') \in {{\bar E}_{train}}} \right\}}}} }  \\
& + {\lambda _{i,i',t,t',k,k'}} \cdot {1_{\left\{ {(i,i',t,t',k,k') \in {E_{res}}} \right\}}} \Bigg ] x_{i,i',t,t',k,k'}^a\\
& + \sum\limits_{(i,i',t,t',k,k') \in E} {\left( {\sum\limits_a {\sum\limits_{l \in \Omega \left( a \right)} {{1_{\left\{ {(i,i',t,t',k,k') \in \Phi \left( {a,l} \right)} \right\}}}{\mu _{a,l}}M}  - {\lambda _{i,i',t,t',k,k'}}M'} } \right)} {y_{i,i',t,t',k,k'}} \\
& + \sum\limits_{(i,i',t,t') \in {\bar E_{train}}} {{\rho _{i,i',t,t'}}{Cap_{i,i',t,t'}}} - \sum\limits_a {\sum\limits_{l \in \Omega \left( a \right)} {{\mu _{a,l}}\left[ {\sum\limits_{\left( {i,i',t,t',k,k'} \right) \in \Phi \left( {a,l} \right)} {\left( {{c_{i,i',t,t',k,k'}} + M} \right)}  + \varepsilon \left( a \right)} \right]} } 
\end{split}
\label{LR-rearrangement}
\end{equation}
\begin{itemize}
\item 指示函数 ${{1_{\left\{ {(i,i',t,t') \in {\bar E_{train}}} \right\}}}}$ 等于 1 表示 $(i,i',t,t')$ 是一个列车服务区段；否则，它等于0。
\item 指示函数 ${1_{\left\{ {(i,i',t,t',k,k') \in \Phi \left( {a,l} \right)} \right\}}}$ 等于 1 表示弧段 $(i,i',t,t',k,k')$ 属于旅客  $a$ 的路径 $l$；否则它等于0。
\end{itemize}

新的拉格朗日函数的第一项 $L\left( {\boldsymbol{x},\boldsymbol{w}} \right)$ 仅仅与 $\boldsymbol{x}$ 有关，第二项仅与 $\boldsymbol{y}$ 有关，而第三、四项都是常数。所以，拉格朗日松弛问题可以分为两类独立的子问题求解。

\textbf{(1) 旅客的最小费用路径问题}

与 $\boldsymbol{x}$ 有关的子问题是最短路径的问题形式，其中，新的弧段成本 $c'_{i,i',t,t',k,k'} = {{z_{i,i',t,t',k,k'}^a} + \sum\limits_{l \in \Omega \left( a \right)} {{\mu _{a,l}}} {c_{i,i',t,t',k,k'}} + {\rho _{i,i',t,t'}} \cdot {1_{\left\{ {(i,i',t,t') \in {\bar E_{train}}} \right\}}} + {\lambda _{i,i',t,t',k,k'}} \cdot {1_{\left\{ {(i,i',t,t',k,k') \in {E_{res}}} \right\}}}}$。这类子问题记为 $(\text{LR-RDP-}\boldsymbol{x})$ 问题，其形式为： 
\begin{equation*}
\begin{split}
& (\text{LR-RDP-}\boldsymbol{x}) \\
& \mathop{min}\limits_{\boldsymbol{x}} \sum\limits_a \sum\limits_{(i,i',t,t',k,k') \in E} \left[ {z_{i,i',t,t',k,k'}^a} + \sum\limits_{l \in \Omega \left( a \right)} {{\mu _{a,l}} {c_{i,i',t,t',k,k'}} + {\rho _{i,i',t,t'}} \cdot {1_{\left\{ {(i,i',t,t') \in {\bar E_{train}}} \right\}}}} \right. \\
& \ \ \  \left.+ \lambda _{i,i',t,t',k,k'} \cdot 1_{\left\{ {(i,i',t,t',k,k') \in E_{res}} \right\}} \right] x_{i,i',t,t',k,k'}^a
\end{split}
\end{equation*}
\hspace{10mm}s.t. (\ref{passenger-conservation}), (\ref{bin1}).

\textbf{(2) 动态价格系统的最大费用路径问题}

基于式(\ref{LR-rearrangement})，拉格朗日松弛问题的另一个子问题形式为：
\begin{equation*}
\mathop {min}\limits_{\boldsymbol{w}}  \sum\limits_{(i,i',t,t',k,k') \in E} {\left( {\sum\limits_a {\sum\limits_{l \in \Omega \left( a \right)} {{1_{\left\{ {(i,i',t,t',k,k') \in \Phi \left( {a,l} \right)} \right\}}}{\mu _{a,l}}M}  - {\lambda _{i,i',t,t',k,k'}}M'} } \right)} {y_{i,i',t,t',k,k'}}
\end{equation*}
\hspace{10mm}s.t. (\ref{price-control}), (\ref{price-path}) and (\ref{bin2}).

接下来，在式(\ref{price-control})中将 $w$ 替换 $y$。为了表达简便，令
\begin{equation}
\hat c \left( {i,i',t,t',k,k'} \right) = {\sum\limits_a {\sum\limits_{l \in \Omega \left( a \right)} {{1_{\left\{ {(i,i',t,t',k,k') \in \Phi \left( {a,l} \right)} \right\}}}{\mu _{a,l}}M}  - {\lambda _{i,i',t,t',k,k'}}M'} }
\end{equation}

这个子问题的目标函数可以写为：
\begin{equation}
\sum\limits_{(i,i',t,t',k,k') \in E} {\hat c \left( {i,i',t,t',k,k'} \right)} {y_{i,i',t,t',k,k'}}
\end{equation}

在式 (\ref{price-control})中通过 $w$ 替换 $y$ ，它变为：
\begin{equation}
\begin{split}
& \sum\limits_{(i,i',t,t',k,k') \in {E_{res}}} {\hat c \left( {i,i',t,t',k,k'} \right)} \sum\limits_{h \in K} {\sum\limits_{\tau  \leqslant t} {\sum\limits_{\tau ' > t} {\sum\limits_m {\delta _{i,i',t,t',k,k'}^mw_{\tau ,\tau ',k',h}^{i,m}} } } }  \\
& \ \ \ + {\sum _{(i,i',t,t',k,k') \in E\backslash {E_{res}}}}\hat c \left( {i,i',t,t',k,k'} \right)
\end{split}
\end{equation}

其中第二项可以省略，因为它与 $w$ 无关。

\begin{equation}
\begin{split}
& \ \sum\limits_{(i,i',t,t',k,k') \in {E_{res}}} {\hat c \left( {i,i',t,t',k,k'} \right)} \sum\limits_m {\sum\limits_{h \in K} {\sum\limits_{\tau  \leqslant t} {\sum\limits_{\tau ' > t} {\delta _{i,i',t,t',k,k'}^mw_{\tau ,\tau ',k',h}^{i,m}} } } } \\
= & \sum\limits_{h \in K} {\sum\limits_\tau  {\sum\limits_{\tau '} {\sum\limits_m {\sum\limits_{(i,i',t,t',k,k') \in {E_{res}}} {{1_{\left\{ {\tau  \leqslant t,\tau ' > t} \right\}}}\hat c \left( {i,i',t,t',k,k'} \right)} \delta _{i,i',t,t',k,k'}^m w_{\tau ,\tau ',k',h}^{i,m}} } } }  \\
= & \sum\limits_j {\sum\limits_m {\sum\limits_{h' \in K} {\sum\limits_{h \in K} {\sum\limits_\tau  {\sum\limits_{\tau '} {\left[ {\sum\limits_{(i,i',t,t',k,k') \in {E_{res}}} {{1_{\left\{ {\tau  \le t,\tau ' > t,j = i,h' = k'} \right\}}}\hat c \left( {i,i',t,t',k,k'} \right)\delta _{i,i',t,t',k,k'}^m} } \right]w_{\tau ,\tau ',h',h}^{j,m}} } } } } } \\
= & \sum\limits_j {\sum\limits_m {\sum\limits_{\left( {\tau ,\tau ',h,h'} \right) \in E'} {\left[ {\sum\limits_{(i,i',t,t',k,k') \in {E_{res}}} {{1_{\left\{ {\tau \le t,\tau ' > t,j = i,h = k'} \right\}}}\hat c \left( {i,i',t,t',k,k'} \right)\delta _{i,i',t,t',k,k'}^m} } \right]w_{\tau ,\tau ',h,h'}^{j,m}} } }  
\end{split}
\end{equation}

通过以上变换，此问题的新形式如下所示，记为 $(\text{LR-RDP-}\boldsymbol{w})$ 问题。
\begin{equation*}
\begin{split}
& (\text{LR-RDP-}\boldsymbol{w})\\
& \mathop {min}\limits_{\boldsymbol{w}} \sum\limits_j {\sum\limits_m {\sum\limits_{\left( {\tau ,\tau ',h,h'} \right) \in E'} {\left[ {\sum\limits_{(i,i',t,t',k,k') \in {E_{res}}} {{1_{\left\{ {\tau  \le t,\tau ' > t,j = i,h = k'} \right\}}}\delta _{i,i',t,t',k,k'}^m} } \right.} } } 
\\
& \left. {\left( {\sum\limits_a {\sum\limits_{l \in \Omega \left( a \right)} {{1_{\left\{ {(i,i',t,t',k,k') \in \Phi \left( {a,l} \right)} \right\}}}{\mu _{a,l}}M}  - {\lambda _{i,i',t,t',k,k'}}M'} } \right)} \right]w_{\tau ,\tau ',h,h'}^{j,m}
\end{split}
\end{equation*}
\hspace{10mm}s.t.(\ref{price-path})(\ref{bin2}).
\begin{itemize}
\item 指示函数 $1_{\left\{ { \left( {i,i',t,t',k,k'} \right) \in E_{res}, j = i,h = k',\tau  \le t,\tau ' > t} \right\}}$ 等于 1 如果 $\left( {i,i',t,t',k,k'} \right) \in E_{res}$, $j = i$, $h = k$, $\tau  \le t$ 和 $\tau ' > t$ 同时成立；否则，它的值为0。
\end{itemize}

$(\text{LR-RDP-}\boldsymbol{w})$ 问题可以理解为在价格-时间网络中找到一条费用最小的路径。由于这两个子问题的形式都是最短路问题，所以在求解中可以采取较为有效的动态规划算法进行求解。

\subsection{解修复算法} \label{sol-fix}

本章采用了一个简单的解修复启发式规则将 LR-RDP-$\boldsymbol{x}$ 转化为可行解。它的基本思想是根据旅客开始购票的时间先后将旅客分配到价格-时空网络上。对于使用了不可行的弧段进行出行的旅客，按照当前的最小费用路径重新进行路径选择。算法\ref{alg:5-2} 记录了解修复的主要步骤。

\begin{algorithm}[H]
\caption{解修复启发式方法}
\label{alg:5-2}
\begin{algorithmic}[1]
\STATE 输入不可行解 $(\boldsymbol{x},\boldsymbol{w})$。
\STATE 初始化价格-时空网络 $(V,E)$ 根据 $\boldsymbol{w}$ 删去不可行的弧段。
\STATE 初始化每条弧段上的流量 $s_{i,i',t,t'} = 0, \ \ \ \forall (i,i',t,t') \in {\bar E_(i,i',t,t')}$
\STATE 设置当前出行旅客 $a$ 为第一个购票的旅客。
\REPEAT
	\IF {旅客 $a$ 的路径是可行的} 
		\STATE 更新旅客 $a$ 经过的每一条弧段的流量 $s_{i,i',t,t'} \leftarrow s_{i,i',t,t'} + 1$；
		\STATE 当 $s_{i,i',t,t'} = Cap_{i,i',t,t'}$ 时，删除所有弧段 $(i,i',t,t',k,k') \in E, \forall k,k'$；
		\STATE 将旅客 $a$ 的路径记录至新的解 $\boldsymbol{x}'$ 中。
	\ELSE
		\STATE 在当前网络 $(V,E)$ 中找最小费用路径；
		\STATE 如果最小费用路径存在且满足 (\ref{brue})，将这条路径加入到新的解 $\boldsymbol{x}'$ 中；
		\STATE 否则算法结束，记录为没有找到可行解。
    \ENDIF
	\STATE 将当前旅客 $a$ 设置为下一个购票的旅客。
\UNTIL $a$ 是最后一位旅客
\STATE 输出新的解 $\boldsymbol{x}'$.
\end{algorithmic}
\end{algorithm}


\subsection{次梯度方法} \label{sub-gra}

次梯度法通常用于求解拉格朗日乘子问题\cite{Ahuja-335,LiMirchandani-929,LiuZhou-931}。次梯度法的计算过程如算法\ref{alg:5-1}所示。在每次迭代中，拉格朗日乘子的迭代方向 ${\rho_{i,i',t,t'}}$, ${\mu _{a,l}}$ 和 $\lambda _{i,i',t,t',k,k'}$ 通过求解拉格朗日松弛问题得到。通过设置步长为 $ \alpha ^n = 1/(n + 1)$ 可以保证算法收敛。
 
\begin{algorithm}[H]
\caption{求解动态价格问题的次梯度法}
\label{alg:5-1}
\begin{algorithmic}[1]
\STATE 设置当前迭代计数 $n = 0$。
\STATE 通过问题输入的时刻表和价格等级生成价格-时空网络。
\STATE 根据价格等级和动态价格调整频率生成价格-时间网络。
\STATE 设置拉格朗日乘子 ${\mu _{a,l}^0}$, $\rho _{i,i',t,t'}^0$ 和 ${\rho _{i,i',t,t'}^0}$ 的初始值为0。
\REPEAT
\STATE 更新价格-时空网络中的弧段成本，计算 $(\text{LR-RDP-}\boldsymbol{x})$。
\STATE 更新价格-时间网络中的弧段成本，计算 $(\text{LR-RDP-}\boldsymbol{w})$。
\STATE 计算拉格朗日松弛问题 $\text{(LR-DRP)}$ 的目标值作为下界。
\STATE 通过解修复方法生成可行解，如果能够找到可行解，则作为问题的上界。 
\STATE 通过式(\ref{subgradientmu})-(\ref{subgradientlambda})计算次梯度。
\begin{align}
& \nabla {\mu _{a,l}}  =  \sum\limits_{\left( {i,i',t,t',k,k'} \right) \in E} {{c_{i,i',t,t',k,k'}}} x_{i,i',t,t',k,k'}^a \nonumber\\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \;  - \sum\limits_{\left( {i,i',t,t',k,k'} \right) \in \Phi \left( {a,l} \right)} {\left[ {{c_{i,i',t,t',k,k'}} + \left( {1 - {y_{i,i',t,t',k,k'}}} \right)M} \right]}  - \varepsilon \left( a \right)
\label{subgradientmu}
\\
& \nabla {\rho _{i,i',t,t'}} =  \sum\limits_a {\sum\limits_{k,k'} {x_{i,i',t,t',k,k'}^a - Ca{p_{i,i',t,t'}}} }
\label{subgradientrho}
\\
&
\nabla {\lambda _{i,i',t,t',k,k'}} =  \sum\limits_a {x_{i,i',t,t',k,k'}^a}  - {y_{i,i',t,t',k,k'}}M'
\label{subgradientlambda}
\end{align}
\STATE 通过式 (\ref{updatemu})-(\ref{updatelambda}) 更新拉格朗日乘子，其中 $\alpha ^n$ 是迭代步长，通过 $ \alpha ^n = 1/(n + 1$) 计算。
\begin{align}
& \mu _{a,l}^{n+1} = \max \left\{ {0,\mu _{a,l}^n + {\alpha ^n} \times \nabla {\mu _{a,l}}} \right\}
\label{updatemu}
\\
& \rho _{i,i',t,t'}^{n + 1} = \max \left\{ {0,\rho _{i,i',t,t'}^n + {\alpha ^n} \times \nabla {\rho _{i,i',t,t'}}} \right\}
\label{updaterho}
\\
& \lambda _{i,i',t,t',k,k'}^{n + 1} = \max \left\{ {0,\lambda _{i,i',t,t',k,k'}^n + {\alpha ^n} \times \nabla {\lambda _{i,i',t,t',k,k'}}} \right\}
\label{updatelambda}
\end{align}
\STATE 更新迭代计数 $n=n+1$。
\UNTIL 算法的迭代次数$n$到达了迭代次数上界，或者上下界之间的间隙小于一个阈值。
\end{algorithmic}
\end{algorithm}

\subsection{割平面法} \label{cuttingplane}
另一种求解拉格朗日乘子问题的方法是割平面法。首先，引入一个辅助变量 $\theta$ 并且构造拉格朗日乘子问题的等价形式：
\begin{equation}
\begin{split}
& \mathop {\max}\limits_{\theta ,{\boldsymbol{\mu}},{\boldsymbol{\rho}},{\boldsymbol{\lambda}}} \theta  \\
& s.t.\;\theta  \leqslant L\left({{{\boldsymbol{x}}},{{\boldsymbol{w}}},{\boldsymbol{\mu }},{\boldsymbol{\rho }},{\boldsymbol{\lambda }}} \right),\;\forall ({\boldsymbol{x}},{\boldsymbol{w}}) \in P \\
& {\boldsymbol{\mu }},{\boldsymbol{\rho }},{\boldsymbol{\lambda }} \geqslant 0.
\nonumber
\end{split}
\end{equation}

其中 $P$ 表示拉格朗日松弛问题的所有可行解$({\boldsymbol{x}},{\boldsymbol{w}})$的集合。割平面的基本思想是在上述问题中，不需要遍历全集 $P$ 而是尝试找到它的一个子集并且能够与原问题有相同的最优目标值。令 $P' \subseteq P$ 构建割平面法主问题如下。

\begin{equation}
\begin{split}
& \mathop {\max}\limits_{\theta ,{\boldsymbol{\mu}},{\boldsymbol{\rho}},{\boldsymbol{\lambda}}} \theta  \\
& \text{s.t.} \; \theta  \leqslant L\left({{{\boldsymbol{x}}},{{\boldsymbol{w}}},{\boldsymbol{\mu }},{\boldsymbol{\rho }},{\boldsymbol{\lambda }}} \right),\;\forall ({\boldsymbol{x}},{\boldsymbol{w}}) \in P' \\
& {\boldsymbol{\mu }},{\boldsymbol{\rho }},{\boldsymbol{\lambda }} \geqslant 0 
\nonumber
\end{split}
\end{equation}

割平面法从一组与初始乘子 $({\boldsymbol{x}}^0,{\boldsymbol{w}}^0)$ 相对的约束开始，此时 $P'=\{ ({\boldsymbol{x}}^0,{\boldsymbol{w}}^0) \}$。然后在第 $n$ 次迭代中，通过求解拉格朗日松弛问题可得 $({\boldsymbol{x}}^n,{\boldsymbol{w}}^n)$。如果割平面主问题与对偶函数 $\theta^n - q({\boldsymbol{\mu }^n},{\boldsymbol{\rho }^n},{\boldsymbol{\lambda }^n})$ 的间隙足够小，那么可以说割平面问题达到最优，否则令 $P'\leftarrow P' \bigcup \{ ({\boldsymbol{x}}^n,{\boldsymbol{w}}^n) \}$，向割平面主问题中增加新的约束 $\theta  \leqslant L\left({{{\boldsymbol{x}}^n},{{\boldsymbol{w}}^n},{\boldsymbol{\mu }},{\boldsymbol{\rho }},{\boldsymbol{\lambda }}} \right)$。

\begin{figure}[htbp]
\centering
\includegraphics[width=\textwidth]{Fig_5-8.png}
\bicaption[fig:5-8]{割平面法示意}{割平面法示意}{Fig}{Illustrations of cutting plane method}
\end{figure}

然而，使用割平面法容易出现不稳定的情况 (后一次的解差于前一次迭代的解) \cite{Baptiste1993}。 例如，假设有一个一维的拉格朗日乘子 $\lambda$ (这里暂时允许混用符号) 并且有6个约束，如图\ref{fig:5-8}(a)所示。约束被加入割平面主问题的顺序写在约束的右边 (``0" 表示初始约束)。迭代路径为 $\lambda^0 \rightarrow \lambda^1 \rightarrow \lambda^2 \rightarrow \lambda^3 \rightarrow \lambda^4$。在这个路径中，对偶函数值 $q(\lambda)$ 先增加然后减少。

一个稳定的算法是通过增加置信范围(trust region)的割平面法。它的基本思想是在迭代中对下一次的乘子 $\lambda^{n+1}$ 迭代的范围进行约束，限制在以当前值 $\lambda^n$ 为中心的一个长度为 $\Delta$ 范围内。也就是说，在第 $n+1$ 次迭代的割平面的主问题中增加约束 $\lambda^{n}-\Delta \leqslant \lambda \leqslant \lambda^{n}+\Delta$。图\ref{fig:5-8}(b) 展示了采用了一个设置较好的置信范围割平面法。与纯粹的割平面法相比，它只用了3步就达到最优，跳过了原来的第二步。然而如果置信范围的大小选取的太小，也会需要更多的迭代才能达到最优，如图\ref{fig:5-8}(c)所示。

为了解决这个问题，本节采用了试算置信范围的方法\cite{KallehaugeLarsen-922}。在第 $n$ 次迭代中，首先求解主问题得到解 $u^{n+1}$。然后，通过式 (\ref{ratio}) 得到参数 $\beta_n$， 以此决定拉格朗日乘子和下一次置信范围的大小。图\ref{fig:5-8}(d)展示了可变置信范围大小的方法。
\begin{equation}
\beta_n = {q(u^{n+1})-q(\lambda^n) \over {\theta_{n+1}-q(\lambda^n)}}
\label{ratio}
\end{equation}

调整置信范围的规则有：
\begin{itemize}
\item 如果 $\beta_n > 0$，$\theta$ 的值能够获得改进，主问题的解可以作为新的乘子值，在本例中即 $\lambda_{n+1}=u_{n+1}$；
\item 如果目标函数值没有获得改进，那么令 $\Delta \leftarrow \Delta /3$，乘子值保持不变，即 $\lambda_{n+1}=\lambda_{n}$；
\item 特别地，如果 $\beta_n = 1$，令 $\Delta \leftarrow \Delta * 2$。
\end{itemize}

现在可以将这个方法应用于求解动态价格问题。割平面法的流程如算法\ref{alg:5-3}所示。综上所述，整个求解动态价格问题的方法框架如图\ref{fig:5-9}所示。

\begin{figure}[htbp]
\centering
\includegraphics[width=\textwidth]{Fig_5-9.png}
\bicaption[fig:5-9]{求解框架}{求解框架}{Fig}{Solution framework}
\end{figure}

\begin{algorithm}[H]
\caption{通过可变置信范围割平面法求解动态价格问题}
\label{alg:5-3}
\begin{algorithmic}[1]
\STATE 初始化前4步骤和次梯度法相同。
\STATE 设置置信范围大小为 $\Delta = 1$。
\STATE 设置约束集合为空 $P' = \emptyset$。
\REPEAT
\STATE 求解拉格朗日松弛问题，步骤与次梯度法相同，得到问题的上下界。
\STATE 令 $({\boldsymbol{x}}^n,{\boldsymbol{w}}^n)$ 表示拉格朗日松弛问题的解。更新 $P'\leftarrow P' \bigcup \{ ({\boldsymbol{x}}^n,{\boldsymbol{w}}^n) \}$，即增加一组约束 $\theta  \leqslant L\left({{{\boldsymbol{x}}^n},{{\boldsymbol{w}}^n},{\boldsymbol{\mu }},{\boldsymbol{\rho }},{\boldsymbol{\lambda }}} \right)$ 至主问题中。
\STATE 求解增加了约束 (\ref{trustregionmu})-(\ref{trustregionlambda})的主问题。最优的目标函数为 $\theta_{n + 1}$，最优解为 $({{{\boldsymbol{\hat \mu }}}^{n + 1}},{{{\boldsymbol{\hat \rho }}}^{n + 1}},{{{\boldsymbol{\hat \lambda }}}^{n + 1}})$。
\begin{align}
& \mu _{a,l}^{n}-\Delta \leqslant \mu _{a,l} \leqslant \mu _{a,l}^{n}+\Delta ,\;\;\;\forall a,l \in \Omega \left( a \right) \label{trustregionmu}\\
&\rho _{i,i',t,t'}^{n}-\Delta \leqslant \rho _{i,i',t,t'} \leqslant \rho _{i,i',t,t'}^{n}+\Delta, \;\;\;\forall (i,i',t,t') \in {{\bar E_{train}}}
\label{trustregionrho}\\
& \lambda _{i,i',t,t',k,k'}^{n}-\Delta \leqslant \lambda _{i,i',t,t',k,k'} \leqslant \lambda _{i,i',t,t',k,k'}^{n}+\Delta,\;\;\;\forall (i,i',t,t',k,k') \in {E_{res}}
\label{trustregionlambda}
\end{align}
\STATE 通过式(\ref{rdpratio})计算 $\beta$。
\begin{equation}
{\beta _n} = {{q({{{\boldsymbol{\hat \mu }}}^{n + 1}},{{{\boldsymbol{\hat \rho }}}^{n + 1}},{{{\boldsymbol{\hat \lambda }}}^{n + 1}}) - q({{\boldsymbol{\mu }}^n},{{\boldsymbol{\rho }}^n},{{\boldsymbol{\lambda }}^n})} \over {{\theta _{n + 1}} - q({{\boldsymbol{\mu }}^n},{{\boldsymbol{\rho }}^n},{{\boldsymbol{\lambda }}^n})}}
\label{rdpratio}
\end{equation}
\STATE 通过以下规则更行拉格朗日乘子。
\IF { $\beta_n > 0$} 
	\STATE 更新 $({{\boldsymbol{\mu }}^{n+1}},{{\boldsymbol{\rho }}^{n+1}},{{\boldsymbol{\lambda }}^{n+1}})=({{{\boldsymbol{\hat \mu }}}^{n + 1}},{{{\boldsymbol{\hat \rho }}}^{n + 1}},{{{\boldsymbol{\hat \lambda }}}^{n + 1}})$；
	\STATE 特别地，如果 $\beta_n = 1$，则 $\Delta \leftarrow \Delta * 2$。
\ELSE 
	\STATE 更行 $\Delta \leftarrow \Delta /3$ 和 $({{\boldsymbol{\mu }}^{n+1}},{{\boldsymbol{\rho }}^{n+1}},{{\boldsymbol{\lambda }}^{n+1}})=({{\boldsymbol{\mu }}^{n}},{{\boldsymbol{\rho }}^{n}},{{\boldsymbol{\lambda }}^{n}})$。
\ENDIF
\STATE 更行迭代计数 $n=n+1$。
\UNTIL 算法停止条件：\\
 (1) 算法迭代此时 $n$ 达到上限值 \\
 (2) 算法上下界的值的间隙小于预设阈值 \\
 (3) 割平面主问题达到最优，即 ${{\theta _{n + 1}} - q({{\boldsymbol{\mu }}^n},{{\boldsymbol{\rho }}^n},{{\boldsymbol{\lambda }}^n})} \leqslant \delta $。这里 $\delta$ 是一个预设的很小的正数。
\end{algorithmic}
\end{algorithm}

\section{模型拓展} \label{disscuession}

\subsection{考虑订票的能力限制}

当有大量旅客在同一时间购票的时候，客票预订系统的处理能力就要被考虑在模型之内了。在我国铁路的实践中，在购票的高峰时间段（比如春节前夕或者周五），几百万的购票请求会涌入购票系统，给订票系统带来非常大的工作量。为了应对这种情况，购票系统增加了排队等待机制。

购票请求处理能力可以通过为预定弧段设置能力限制来体现，如式(\ref{reservation-capacity})所示。为了处理这条约束，可以增加一类新的乘子。

\begin{equation}
\sum\limits_a {\sum\limits_{i,i',t',k,k'} {x_{i,i',t,t',k,k'}^a \le {Cap_t}} } ,\;\;\;\forall t \in [0,T_R-1]
\label{reservation-capacity}
\end{equation}
\begin{itemize}
\item $Cap_t$ 表示在时间段 $[t,t+1]$ 的最大处理购票请求数量。
\end{itemize}

\subsection{考虑旅客上下车的时间}

在列车的经停站，旅客上车和下车的数量不能太多，因为很多中间站的停站时间并不长。所以从这些车站出发和到达的车票销售上限需要被限制。

\begin{equation}
\sum\limits_a {\sum\limits_{\left( {i,i',t,t',k,k'} \right) \in {E_{res}} \cup \;{E_{finish}}:i = j} {\delta _{i,i',t,t',k,k'}^mx_{i,i',t,t',k,k'}^a} }  \le N_j^m, \ \ \ \forall m,j
\end{equation}
\begin{itemize}
\item $N_j^m$ 表示列车 $m$ 在 $j$ 站的最大上下车人数。
\end{itemize}

\subsection{考虑旅客的出行成本限制}
除了采用有限理性的方式描述旅客的选择行为，旅途的成本上限也是在建模中经常考虑的约束。令 $B^a$ 表示旅客 $a$ 的出行成本，旅行的成本约束可以表示为式(\ref{travel-time-budget})。
\begin{equation}
\sum\limits_{(i,i',t,t',k,k') \in E} {{c_{i,i',t,t',k,k'}}x_{i,i',t,t',k,k'}^a}  \le {B^a}
\label{travel-time-budget}
\end{equation}

\subsection{与上限式控制的结合}

本章考虑的建模方法也可以与上限式的控制结合起来。为了表达对车票的可售性控制，需要引入一个新的价格等级 ${k_\infty }$，在这个价格等级中，所有列车服务区段的能力均为0。加入新的价格等级后，价格等级的集合变为 $K'' = K  \cup \{ {k_\infty} \}$。

\section{算例} \label{compute_result}

这一节对比了三种不同的求解方法（次梯度法、割平面法和带有置信范围的割平面法）在求解过程中的拉格朗日乘子和上下界的变化。问题的求解程序通过 C\# 实现，并运行在一台 16 核心 (32 线程) 128 GB 内存的计算机上。

\subsection{数据准备}

本章的案例采用的路网由一条线路5个车站A、B、C、D、E构成。其中运行了2列车，列车1和列车2。它们都从车站A出发前往车站E，经停B、C、D站。在这个案例中，列车1运行速度较高，而列车2运行速度较低，每个区间比列车1多运行5分钟。列车1的席位数是40，而列车2的席位数为100.每个列车区间的基础成本价格都是100。

%\begin{figure}[htbp]
%\centering
%\includegraphics[width=0.8\textwidth]{Fig_5-13.png}
%\bicaption[fig:5-13]{实验数据示意}{实验数据示意}{Fig}{The timetable for experiment}
%\end{figure}

假设预售期为两个小时。旅客的到达时间已知，且他们的到达分布如图\ref{fig:5-14}所示。旅客对路径的成本与最短路的容忍度 $\varepsilon \left( a \right)$ 为一个很大的正数，所以旅客可以选择所有可行路径。旅客的时间成本设置为预售期 0.01 (元/分钟) 和 乘车时 0.5 (元/分钟)。

\begin{figure}[htbp]
\centering
\includegraphics[width=\textwidth]{Fig_5-14.png}
\bicaption[fig:5-14]{旅客到达时间示意}{旅客到达时间示意}{Fig}{The arrival times of passengers}
\end{figure}


车票价格调整的间隔设置为60分钟，即价格在预售期内只变化一次。案例供考虑三种价格等级，分别是 $\{ 0.8, 1 ,1.2\}$ (八折、原价和上涨20\%)。预售期内的时间尺度为1分钟，一共有120个离散时间。

\subsection{结果分析}

实验的初始拉格朗日乘子值被设置为0。经过分别采用这三种求解方法进行计算，结果如图\ref{fig:5-12}所示。左侧的图表示上界和下界的变化情况，右边的图表示拉格朗日乘子  ${\rho_{i,i',t,t'}}$ 的变化（列车1的第一个列车服务区间）。次梯度求解方法运行了50步之后还未收敛。随着步长 $ \alpha ^n$ 拉格朗日乘子的震荡不断缩小。割平面法经过了32次迭代之后达到最优。带置信范围的次梯度法经过了29次迭代达到最优。在迭代过程中，拉格朗日乘子和问题下界的变化相比前面两种方法更加的平滑。问题上下界之间的间隙如表\ref{tab:6-1}所示。

\begin{figure}[H]
\centering
\includegraphics[width=0.7\textwidth]{Fig_5-12.png}
\bicaption[fig:5-12]{求解方法对比}{求解方法对比}{Fig}{Performace of differenct solution method}
\end{figure}

\begin{table}[htbp]
\centering
\bicaption[tab:6-1]{求解时间和上下界间隙}{求解时间和上下界间隙}{Table}{Time Cost and Gap}
\begin{tabular}{l|l|l|l}
	\hline
	          & 次梯度法   & 割平面法   & 带有置信范围的割平面法 \\ \hline
	求解时间 (分钟) & 75     & 49     & 44          \\ \hline
	上下界间隙     & 0.48\% & 0.43\% & 0.29\%      \\ \hline
\end{tabular}
\end{table}

\section{本章小节} \label{conclution}

本章研究了通过网络模型求解态价格问题的方法。通过构建价格-时空网络和价格-时间网络，分别在建模中考虑了旅客行为和产品价格变化。相比于第四章的模型，采用网络表达的优点在于能够考虑旅客的购票中的等待时间，即旅客从进入购票系统到购买车票的这一段时间。本章建立整数规划模型，构造列车能力约束，旅客的有限理性选择约束和动态价格控制逻辑约束，将旅客行为与动态价格联系起来。

本章应用拉格朗日松弛技术，将原问题分解为两类最小费用路径问题。其中，拉格朗日乘子问题通过引入置信范围的割平面法求解。实验表明，这种方法可以在短时间内得到更好的解，并且求解的过程更加稳定。
